package 回溯;

import java.util.*;
//https://leetcode.cn/problems/n-queens/

public class N皇后 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> list = new ArrayList<>();
      //存放行信息节点，就是每行的皇后都在哪个位置，因为每行只能放一个所以定义n个就好了
        // 这里需要初始化一下默认是0；但是0我们要用有第0行列嘛，我们初始化为-1；
        int[] cur = new int[n];
      //初始化
        Arrays.fill(cur , -1);
        Set<Integer> row = new HashSet<>();
        Set<Integer> lht = new HashSet<>();
        Set<Integer> rht = new HashSet<>();
        fun(list , cur , n ,0 , row , lht , rht);
        return list;
    }

    private void fun(List<List<String>> list, int[] cur, int n , int dis, Set<Integer> row, Set<Integer> lht, Set<Integer> rht) {
        if (dis == n){
            List<String> back = backValue(cur , n);
            list.add(back);
        }else {
            for (int i = 0; i < n; i++) {
                if (row.contains(i)){
                    continue;
                }
                int lhtV = dis - i;
                if (lht.contains(lhtV)){
                    continue;
                }
                int rhtV = dis + i;
                if (rht.contains(rhtV)){
                    continue;
                }
                cur[dis] = i;
                row.add(i);
                lht.add(lhtV);
                rht.add(rhtV);
                fun(list , cur , n , dis + 1 , row , lht , rht);
                cur[dis] = -1;
                row.remove(i);
                lht.remove(lhtV);
                rht.remove(rhtV);
            }
        }
    }

    //给之前处理过存有每行皇后所在位置的数组和大小返回成链表
    private List<String> backValue(int[] cur, int n) {
        List<String> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row , '.');
            row[cur[i]] = 'Q';
            arr.add(new String(row));
        }
        return arr;
    }

}
